package com.taldh.algorithm.二分查找法;

import org.junit.Assert;
import org.junit.Test;

public class searchInsert {

    public int searchInsert(int[] nums, int target) {
        if (target > nums[nums.length - 1]) {
            return nums.length;
        }
        if (target < nums[0]) {
            return 0;
        }
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int half = (i + j) / 2;
            if (nums[half] == target) {
                return half;
            }
            if (half == i && nums[half] < target) {
                return half + 1;
            } else if (half == j && nums[half] > target) {
                return half;
            }
            if (nums[half] < target) {
                i = half;
            } else if (nums[half] > target) {
                j = half;
            }
        }
        return -1;
    }

    @Test
    public void test() {
        Assert.assertEquals(2, searchInsert(new int[]{1,3,5,6}, 5));
        Assert.assertEquals(1, searchInsert(new int[]{1,3,5,6}, 2));
        Assert.assertEquals(4, searchInsert(new int[]{1,3,5,6}, 7));
        Assert.assertEquals(0, searchInsert(new int[]{1,3,5,6}, 0));
        Assert.assertEquals(1, searchInsert(new int[]{1,3,5}, 2));
        Assert.assertEquals(2, searchInsert(new int[]{1,3,5}, 4));
        Assert.assertEquals(0, searchInsert(new int[]{1}, 1));
        Assert.assertEquals(2, searchInsert(new int[]{1,2,4,6,7}, 3));
        Assert.assertEquals(3, searchInsert(new int[]{3,5,7,9,10}, 8));
    }
}